package com.zlp.partice;

import org.junit.Test;

import java.util.*;

/**
 * @Author: zhulaiping
 * @Date: 2021/9/24 9:53
 */
public class Day0924 {

    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }
    public Node flatten(Node head) {
        Node root = head;
        Node temp;
        while (head!=null){
            if(head.child!=null){
                temp = head.next;
                Node cur = getFail(head.child);

                head.next = head.child;
                head.child.prev = head;
                head.child = null;

                cur.next = temp;
                temp.prev = cur;

            }
            head = head.next;

        }
        return root;
    }

    private Node getFail(Node child) {
        while (child.next!=null){
            child = child.next;
        }
        return child;
    }

    public int minDistance(String word1, String word2) {
        int row = word1.length(),column = word2.length();
        int[][] dp = new int[row+1][column+1];
        for (int i=0;i<row;i++){
            for (int j=0;j<column;j++){
                if(word1.charAt(i)==word2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else dp[i+1][j+1] = Math.max(dp[i+1][j],dp[i][j+1]);
            }
        }
        return row+column-2*dp[row][column];
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
    int ret = 0;
    public int pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum);
        return ret;
    }

    private void dfs(TreeNode root, int target) {
        if(root==null) return;
        dfs2(root,0,target);
        dfs(root.left,target);
        dfs(root.right,target);
    }
    private void dfs2(TreeNode root, int val, int target) {
        if(root==null) return;
        if(val==target) {
            System.out.println(root.val);
            ret += 1;
        }
        dfs2(root.left,val+root.val,target);
        dfs2(root.right,val+root.val,target);
    }
    public String destCity(List<List<String>> paths) {
        Set<String> set = new HashSet<>();
        for (List<String> path:paths){
            set.add(path.get(0));
        }
        for (List<String> path:paths){
            if(!set.contains(path.get(1)))
                return path.get(1);
        }
        return "";
    }

    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
            int a = (ax1-ax2)*(ay1-ay2),b = (bx1-bx2)*(by1-by2);
            int x = Math.max(0,Math.max(ax1,bx1)-Math.min(ax2,bx2));
            int y = Math.max(0,Math.max(ay1,by1)-Math.min(ay2,by2));
            return a+b-x*y;
    }

    @Test
    public void ww(){


        System.out.println(cal(-2));
        System.out.println(toHex(-2));
    }
    public String toHex(int num) {
        long val = num>=0?num:(1l<<32)+num;
        char[] map = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        StringBuilder sb = new StringBuilder();
        do {
           sb.append(map[(int)(val%16)]);
           val /= 16;
        }while (val!=0);
        return sb.reverse().toString();
    }

    private long cal(int num) {
        if(num>=0) return num;
        long a = 1l<<32;
        return a + num;
    }

    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        for (int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='-') continue;
            if(cnt % k == 0) {
                sb.append('-');
                cnt=0;
            }
            sb.append(Character.toUpperCase(s.charAt(i)));
            cnt++;
        }
        return sb.reverse().toString();
    }

    public int countSegments(String s) {
        int ret = 0,cnt = 0;
        for (char ch:s.toCharArray()){
            if(ch>='A'&&ch<='Z' || ch>='a'&&ch<='z'){
                cnt++;
            }else {
                if(cnt>0){
                    ret++;
                    cnt = 0;
                }
            }
        }
        return ret;
    }
    class PeekingIterator implements Iterator<Integer> {
        Iterator<Integer> iterator;
        Integer cache;
        public PeekingIterator(Iterator<Integer> iterator) {
            // initialize any member here.
            this.iterator = iterator;
            cache = iterator.next();
        }

        // Returns the next element in the iteration without advancing the iterator.
        public Integer peek() {
            return cache;
        }

        // hasNext() and next() should behave the same as in the Iterator interface.
        // Override them if needed.
        @Override
        public Integer next() {
            Integer temp = cache;
            cache = iterator.hasNext()?iterator.next():null;
            return temp;
        }

        @Override
        public boolean hasNext() {
            return cache==null?false:true;
        }
    }

    public List<String> findRepeatedDnaSequences(String s) {
        if(s.length()<10) return new ArrayList<>();
        int l = 0,r = 9;
        Set<String> set = new TreeSet<>();
        List<String>list = new ArrayList<>();
        while (r<s.length()){
            String s1 = s.substring(l, r);
            if(set.contains(s1)){
                list.add(s1);
            }else {
                set.add(s1);
            }
            ++l;
            ++r;
        }
        return list;
    }

    public int arrangeCoins(int n) {
        long l = 1,r = n;
        while (l<r){
            long mid = l+(r-l+1)/2;
            if(mid*(mid+1)/2>n) r = mid - 1;
            else if(mid*(mid+1)/2<=n) l = mid;
        }
        return (int) l;
    }
}
